package leetcode.One_hundred_to_Two_hundred;

public class Test130被围绕的区域 {
    /**
     * floodfill 算法，遍历数组，第一次发现O之后，就dfs它
     * 如果在dfs的过程中发现O与边界相连了，则此区域内的O不允许被填充
     * 同时此区域内的所有O不再考虑，继续往下遍历直到结束
     *
     * 不管这片被dfs的区域是否触及边界他都被遍历了，不再考虑，所以只需要一个visited[][]
     */

    /**
     * fooldfill 所有边界上的 O 以及其关联的 O，将遍历过的位置记为 true 防止下次再检查
     */

    boolean[][] visited = null;
    int m, n;

    public void solve1(char[][] board) {
        m = board.length;
        if (m == 0) {
            return;
        }
        n = board[0].length;
        visited = new boolean[m][n];
        // 从边界开始遍历
        for (int i = 0; i < m; i++) {
            dfs1(board, i, 0);
            dfs1(board, i, n - 1);
        }

        for (int i = 0; i < n; i++) {
            dfs1(board, 0, i);
            dfs1(board, m - 1, i);
        }

//        for (int i = 0; i < m; i++) {
//            for (int j = 0; j < n; j++) {
//                if (!visited[i][j] && board[i][j] == 'O') {
//                    dfs(board, i, j);
//                }
//            }
//        }

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (!visited[i][j] && board[i][j] == 'O') {
                    dfs2(board, i, j);
                }
            }
        }
    }

    private void dfs1(char[][] board, int x, int y) {
        if (x >= 0 && x < m && y >= 0 && y < n) {
            if (!visited[x][y] && board[x][y] == 'O') {
                visited[x][y] = true;
                //board[x][y] = 'X';
                dfs(board, x + 1, y);
                dfs(board, x - 1, y);
                dfs(board, x, y + 1);
                dfs(board, x, y - 1);
            }
        }
    }

    private void dfs2(char[][] board, int x, int y) {
        if (x >= 0 && x < m && y >= 0 && y < n) {
            if (!visited[x][y] && board[x][y] == 'O') {
                visited[x][y] = true;
                board[x][y] = 'X';
                dfs(board, x + 1, y);
                dfs(board, x - 1, y);
                dfs(board, x, y + 1);
                dfs(board, x, y - 1);
            }
        }
    }


    /*****************************/

    int row, col;
    public void solve(char[][] board) {
        if (board == null || board.length == 0)
            return;
        row = board.length;
        col = board[0].length;
        for (int i = 0; i < row; i++) {    //对第一行和最后一行的所有O进行深度优先搜索
            dfs(board, i, 0);
            dfs(board, i, col - 1);
        }
        for (int j = 0; j < col; j++) {    //对第一列和最后一列的所有O进行深度优先搜索
            dfs(board, 0, j);
            dfs(board, row - 1, j);
        }
        for (int i = 0; i < row; i++) {    //遍历矩阵，将O变为X，将-变为O
            for (int j = 0; j < col; j++) {
                if (board[i][j] == 'O')
                    board[i][j] = 'X';
                if (board[i][j] == '-')
                    board[i][j] = 'O';
            }
        }
        return;
    }

    /**
     * 使用递归进行深度优先搜索
     */
    public void dfs(char[][] board, int i, int j) {
        if (i < 0 || j < 0 || i >= row || j >= col || board[i][j] != 'O')   //递归终止条件判断
            return;
        board[i][j] = '-';    //将当前O更改为-
        dfs(board, i - 1, j);   //递归该点上方的点
        dfs(board, i + 1, j);   //递归该点下方的点
        dfs(board, i, j - 1);   //递归该点左边的点
        dfs(board, i, j + 1);   //递归该点右边的点
    }
}
